home *** CD-ROM | disk | FTP | other *** search
/ Software Vault: The Diamond Collection / The Diamond Collection (Software Vault)(Digital Impact).ISO / cdr47 / lzpip103.zip / DEFLATE.C < prev    next >
Text File  |  1994-02-24  |  30KB  |  814 lines
  1. /*
  2.  The following sorce code is derived from Info-Zip 'zip' 2.01
  3.  distribution copyrighted by Mark Adler, Richard B. Wales,
  4.  Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  5. */
  6.  
  7. /*
  8.  *  deflate.c by Jean-loup Gailly.
  9.  *
  10.  *  PURPOSE
  11.  *
  12.  *      Identify new text as repetitions of old text within a fixed-
  13.  *      length sliding window trailing behind the new text.
  14.  *
  15.  *  DISCUSSION
  16.  *
  17.  *      The "deflation" process depends on being able to identify portions
  18.  *      of the input text which are identical to earlier input (within a
  19.  *      sliding window trailing behind the input currently being processed).
  20.  *
  21.  *      The most straightforward technique turns out to be the fastest for
  22.  *      most input files: try all possible matches and select the longest.
  23.  *      The key feature of this algorithm is that insertions into the string
  24.  *      dictionary are very simple and thus fast, and deletions are avoided
  25.  *      completely. Insertions are performed at each input character, whereas
  26.  *      string matches are performed only when the previous match ends. So it
  27.  *      is preferable to spend more time in matches to allow very fast string
  28.  *      insertions and avoid deletions. The matching algorithm for small
  29.  *      strings is inspired from that of Rabin & Karp. A brute force approach
  30.  *      is used to find longer strings when a small match has been found.
  31.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  32.  *      (by Leonid Broukhis).
  33.  *         A previous version of this file used a more sophisticated algorithm
  34.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  35.  *      time, but has a larger average cost, uses more memory and is patented.
  36.  *      However the F&G algorithm may be faster for some highly redundant
  37.  *      files if the parameter max_chain_length (described below) is too large.
  38.  *
  39.  *  ACKNOWLEDGEMENTS
  40.  *
  41.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  42.  *      I found it in 'freeze' written by Leonid Broukhis.
  43.  *      Thanks to many info-zippers for bug reports and testing.
  44.  *
  45.  *  REFERENCES
  46.  *
  47.  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
  48.  *
  49.  *      A description of the Rabin and Karp algorithm is given in the book
  50.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  51.  *
  52.  *      Fiala,E.R., and Greene,D.H.
  53.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  54.  *
  55.  *  INTERFACE
  56.  *
  57.  *      int lm_init(void)
  58.  *          Initialize the "longest match" routines for a new file
  59.  *
  60.  *      int fast_deflate(char*, unsigned)
  61.  *      int lazy_deflate(char*, unsigned)
  62.  *          Processes a new input file and return its compressed length. Sets
  63.  *          the compressed length, crc, deflate flags and internal file
  64.  *          attributes.
  65.  */
  66.  
  67. #include <stdio.h>
  68. #include "modern.h"
  69. #include "lzpipe.h"
  70. #include "zalloc.h"
  71. #include "zipdefs.h"
  72. #include "zipguts.h"
  73. #ifdef MODERN
  74. #  include <string.h>
  75. #else
  76. #  ifdef pyr /* Pyramid */
  77. #    define ZMEM /* No mem???() functions at all */
  78. #  endif
  79. #endif
  80.  
  81. /* Define this symbol if your target allows access to unaligned data.
  82.  * This is not mandatory, just a speed optimization. The compressed
  83.  * output is strictly identical.
  84.  */
  85. #ifndef UNALIGNED_OK
  86. #  ifdef MSDOS
  87. #   ifndef WIN32
  88. #    define UNALIGNED_OK
  89. #   endif
  90. #  endif
  91. #  ifdef i386
  92. #    define UNALIGNED_OK
  93. #  endif
  94. #  ifdef mc68020
  95. #    define UNALIGNED_OK
  96. #  endif
  97. #  ifdef vax
  98. #    define UNALIGNED_OK
  99. #  endif
  100. #endif
  101.  
  102. /* Compile with MEDIUM_MEM to reduce the memory requirements or
  103.  * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
  104.  * entire input file can be held in memory (not possible on 16 bit systems).
  105.  * Warning: defining these symbols affects HASH_BITS (see below) and thus
  106.  * affects the compression ratio. The compressed output
  107.  * is still correct, and might even be smaller in some cases.
  108.  */
  109.  
  110. #ifdef SMALL_MEM
  111. #   define HASH_BITS  13  /* Number of bits used to hash strings */
  112. #endif
  113. #ifdef MEDIUM_MEM
  114. #   define HASH_BITS  14
  115. #endif
  116. #ifndef HASH_BITS
  117. #   define HASH_BITS  15
  118.    /* For portability to 16 bit machines, do not use values above 15. */
  119. #endif
  120.  
  121. #define HASH_SIZE (unsigned)(1<<HASH_BITS)
  122. #define HASH_MASK (HASH_SIZE-1)
  123. #define WMASK     (WSIZE-1)
  124. /* HASH_SIZE and WSIZE must be powers of two */
  125.  
  126. #define NIL 0
  127. /* Tail of hash chains */
  128.  
  129. #ifndef TOO_FAR
  130. #  define TOO_FAR 4096
  131. #endif
  132. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  133.  
  134. #ifdef ATARI_ST
  135. #  undef MSDOS /* avoid the processor specific parts */
  136.    /* (but the Atari should never define MSDOS anyway ...) */
  137. #endif
  138. #ifdef MSDOS
  139. #  ifndef NO_ASM
  140. #    ifndef ASMV
  141. #      define ASMV
  142. #    endif
  143. #  endif
  144. #endif
  145. #ifdef ASMV
  146. #  ifndef MSDOS
  147. #    ifdef DYN_ALLOC
  148.        #error: DYN_ALLOC not yet supported in match.s
  149. #    endif
  150. #  endif
  151. #endif
  152. #ifdef MSDOS
  153. #  ifndef __32BIT__
  154. #    define MAXSEG_64K
  155. #  endif
  156. #endif
  157.  
  158. /* Local data used by the "longest match" routines. */
  159.  
  160. #if defined(BIG_MEM) || defined(MMAP)
  161.   typedef unsigned Pos; /* must be at least 32 bits */
  162. #else
  163.   typedef ush Pos;
  164. #endif
  165. typedef unsigned IPos;
  166. /* A Pos is an index in the character window. We use short instead of int to
  167.  * save space in the various tables. IPos is used only for parameter passing.
  168.  */
  169.  
  170. #ifndef DYN_ALLOC
  171.   uch    window[2L*WSIZE];
  172.   /* Sliding window. Input bytes are read into the second half of the window,
  173.    * and move to the first half later to keep a dictionary of at least WSIZE
  174.    * bytes. With this organization, matches are limited to a distance of
  175.    * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  176.    * performed with a length multiple of the block size. Also, it limits
  177.    * the window size to 64K, which is quite useful on MSDOS.
  178.    * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
  179.    * be less efficient since the data would have to be copied WSIZE/BSZ times)
  180.    */
  181.   Pos    prev[WSIZE];
  182.   /* Link to older string with same hash index. To limit the size of this
  183.    * array to 64K, this link is maintained only for the last 32K strings.
  184.    * An index in this array is thus a window index modulo 32K.
  185.    */
  186.   Pos    head[HASH_SIZE];
  187.   /* Heads of the hash chains or NIL. If your compiler thinks that
  188.    * HASH_SIZE is a dynamic value, recompile with -DDYN_ALLOC.
  189.    */
  190. #else
  191.    uch  far *window = NULL;
  192.    Pos  far *prev   = NULL;
  193.    Pos  far *head   = NULL;
  194. #endif
  195. #ifndef zalloc
  196.    void far *p_win  = NULL;
  197.    void far *p_prev = NULL;
  198.    void far *p_head = NULL;
  199. #else
  200. #  define p_win  window
  201. #  define p_prev prev
  202. #  define p_head head
  203. #endif
  204.  
  205. #define WINDOW_SIZE ((ulg)2*WSIZE)
  206.  
  207. long block_start;
  208. /* window position at the beginning of the current output block. Gets
  209.  * negative when the window is moved backwards. */
  210.  
  211. static unsigned ins_h;  /* hash index of string to be inserted */
  212. static char uptodate;   /* hash preparation flag */
  213.  
  214. #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
  215. /* Number of bits by which ins_h and del_h must be shifted at each
  216.  * input step. It must be such that after MIN_MATCH steps, the oldest
  217.  * byte no longer takes part in the hash key, that is:
  218.  *   H_SHIFT * MIN_MATCH >= HASH_BITS */
  219.  
  220. unsigned int prev_length;
  221. /* Length of the best match at previous step. Matches not greater than this
  222.  * are discarded. This is used in the lazy match evaluation. */
  223.  
  224.        unsigned strstart;    /* start of string to insert */
  225.        unsigned match_start; /* start of matching string */
  226. static unsigned lookahead;   /* number of valid bytes ahead in window */
  227.        unsigned minlookahead;
  228.  
  229. unsigned max_chain_length;
  230. /* To speed up deflation, hash chains are never searched beyond this length.
  231.  * A higher limit improves compression ratio but degrades the speed. */
  232.  
  233. static unsigned int max_lazy_match;
  234. /* Attempt to find a better match only when the current match is strictly
  235.  * smaller than this value. This mechanism is used only for compression
  236.  * levels >= 4. */
  237.  
  238. #define max_insert_length  max_lazy_match
  239. /* Insert new strings in the hash table only if the match length
  240.  * is not greater than this length. This saves time but degrades compression.
  241.  * max_insert_length is used only for compression levels <= 3. */
  242.  
  243. unsigned good_match;
  244. /* Use a faster search when the previous match is longer than this */
  245.  
  246. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  247.  * the desired pack level (0..9). The values given below have been tuned to
  248.  * exclude worst case performance for pathological files. Better values may
  249.  * be found for specific files. */
  250.  
  251. typedef struct config {
  252.    ush good_length; /* reduce lazy search above this match length */
  253.    ush max_lazy;    /* do not perform lazy search above this match length */
  254.    ush nice_length; /* quit search above this match length */
  255.    ush max_chain;
  256. } config;
  257.  
  258. #ifdef  FULL_SEARCH
  259. # define nice_match MAX_MATCH
  260. #else
  261.   int nice_match; /* Stop searching when current match exceeds this */
  262. #endif
  263.  
  264. static config configuration_table[10] = {
  265. /*      good lazy nice chain */
  266. /* 0 */ {0,    0,  0,    0},  /* store only */
  267. /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
  268. /* 2 */ {4,    5, 16,    8},
  269. /* 3 */ {4,    6, 32,   32},
  270.  
  271. /* 4 */ {4,    4, 16,   16},  /* lazy matches */
  272. /* 5 */ {8,   16, 32,   32},
  273. /* 6 */ {8,   16, 128, 128},
  274. /* 7 */ {8,   32, 128, 256},
  275. /* 8 */ {32, 128, 258, 1024},
  276. /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
  277.  
  278. /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  279.  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  280.  * meaning. */
  281.  
  282. /* Prototypes for local functions. */
  283. static unsigned fill_window OF((char*, unsigned));
  284. static void     init_hash   OF((void));
  285.  
  286. extern int longest_match OF((IPos cur_match));
  287. #ifdef ASMV
  288. extern int match_init OF((void)); /* asm code initialization */
  289. #endif
  290. #ifdef DEBUG
  291. static void check_match OF((IPos start, IPos match, int length));
  292. #endif
  293.  
  294. /* Update a hash value with the given input byte
  295.  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
  296.  *    input characters, so that a running hash key can be computed from the
  297.  *    previous key instead of complete recalculation each time. */
  298. #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
  299.  
  300. /* Insert string s in the dictionary and set match_head to the previous head
  301.  * of the hash chain (the most recent string with same hash key). Return
  302.  * the previous length of the hash chain.
  303.  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  304.  *    input characters and the first MIN_MATCH bytes of s are valid
  305.  *    (except for the last MIN_MATCH-1 bytes of the input file). */
  306. #define INSERT_STRING(s, match_head) \
  307.    (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \
  308.     prev[(s) & WMASK] = match_head = head[ins_h], \
  309.     head[ins_h] = (s))
  310.  
  311. static void init_hash()
  312. {
  313.    register unsigned j;
  314.  
  315.    for (ins_h=0, j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]);
  316.    /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
  317.       not important since only literal bytes will be emitted. */
  318. }
  319.  
  320. #ifdef DYN_ALLOC
  321. void lm_free() /* Free the window and hash table */
  322. {
  323.    if (p_win ) { zfree(p_win ); p_win  = NULL; }
  324.    if (p_prev) { zfree(p_prev); p_prev = NULL; }
  325.    if (p_head) { zfree(p_head); p_head = NULL; }
  326. }
  327.  
  328. int lm_alloc()
  329. {
  330.    if (!p_win) {
  331.       window = (uch*)zalloc(&p_win, WSIZE, 2*sizeof(uch));
  332.       if (!p_win) return ZNOMEM;
  333.    }
  334.    if (!p_prev) {
  335.       prev = (Pos*)zalloc(&p_prev, WSIZE,     sizeof(Pos));
  336.       if (!p_prev) { lm_free(); return ZNOMEM; }
  337.    }
  338.    if (!p_head) {
  339.       head = (Pos*)zalloc(&p_head, HASH_SIZE, sizeof(Pos));
  340.       if (!p_head) { lm_free(); return ZNOMEM; }
  341.    }
  342.    return 0;
  343. }
  344. #endif
  345.  
  346. /* A block of local deflate process data to be saved between
  347.  * sequential calls to deflate functions */
  348. static int match_available = 0; /* set if previous match exists */
  349. static unsigned match_length = MIN_MATCH-1; /* length of best match */
  350.  
  351. /* Initialize the "longest match" routines for a new file */
  352. int lm_init(void)
  353. {
  354. #ifdef ZMEM
  355.    register unsigned j;
  356. #endif
  357. #ifdef DYN_ALLOC
  358.    /* Use dynamic allocation if compiler dislike big static arrays: */
  359.    if (lm_alloc() != 0) return ZNOMEM;
  360. #endif
  361.    /* Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  362.     * prev[] will be initialized on the fly. */
  363. #ifdef ZMEM
  364.    j = 0; do head[j] = NIL; while (++j < HASH_SIZE);
  365. #else
  366.    head[HASH_SIZE-1] = NIL;
  367.    memset((char*)head, NIL, (unsigned)(HASH_SIZE-1)*sizeof(*head));
  368. #endif
  369.    /* Set the default configuration parameters: */
  370.    max_lazy_match   = configuration_table[deflate_level].max_lazy;
  371.    good_match       = configuration_table[deflate_level].good_length;
  372. #ifndef FULL_SEARCH
  373.    nice_match       = configuration_table[deflate_level].nice_length;
  374. #endif
  375.    max_chain_length = configuration_table[deflate_level].max_chain;
  376.  
  377.    strstart = 0;
  378.    block_start = 0L;
  379. #ifdef ASMV
  380.    /* initialize the asm code */ if (match_init() != 0) return ZERROR;
  381. #endif
  382.    lookahead = 0;
  383.    uptodate  = 0;
  384.    minlookahead = MIN_LOOKAHEAD-1;
  385.    match_available = 0;
  386.    prev_length = MIN_MATCH-1;
  387.    return 0;
  388. }
  389.  
  390. /* Set match_start to the longest match starting at the given string and
  391.  * return its length. Matches shorter or equal to prev_length are discarded,
  392.  * in which case the result is equal to prev_length and match_start is
  393.  * garbage.
  394.  * IN assertions: cur_match is the head of the hash chain for the current
  395.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  396.  */
  397. #ifndef ASMV
  398. /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
  399.  * match.s. The code is functionally equivalent, so you can use the C version
  400.  * if desired.  A 68000 version is in amiga/match_68.a -- this could be used
  401.  * with other 68000 based systems such as Macintosh with a little effort.
  402.  */
  403. int longest_match(cur_match)
  404.     IPos cur_match;                             /* current match */
  405. {
  406.    unsigned chain_length = max_chain_length;   /* max hash chain length */
  407.    register uch *scan = window + strstart;     /* current string */
  408.    register uch *match;                        /* matched string */
  409.    register int len;                           /* length of current match */
  410.    int best_len = prev_length;                 /* best match length so far */
  411.    IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL;
  412.    /* Stop when cur_match becomes <= limit. To simplify the code,
  413.       we prevent matches with the string of window index 0. */
  414.  
  415. /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  416.  * It is easy to get rid of this optimization if necessary. */
  417. #if HASH_BITS < 8 || MAX_MATCH != 258
  418.    #error Code too clever
  419. #endif
  420.  
  421. #ifdef UNALIGNED_OK
  422.    /* Compare two bytes at a time. Note: this is not always beneficial.
  423.       Try with and without -DUNALIGNED_OK to check. */
  424.    register uch *strend = window + strstart + MAX_MATCH - 1;
  425.    register ush scan_start = *(ush*)scan;
  426.    register ush scan_end   = *(ush*)(scan+best_len-1);
  427. #else
  428.    register uch *strend = window + strstart + MAX_MATCH;
  429.    register uch scan_end1 = scan[best_len-1];
  430.    register uch scan_end  = scan[best_len];
  431. #endif
  432.  
  433.    /* Do not waste too much time if we already have a good match: */
  434.    if (prev_length >= good_match) {
  435.        chain_length >>= 2;
  436.    }
  437.    Assert(strstart <= WINDOW_SIZE-MIN_LOOKAHEAD, "insufficient lookahead");
  438.  
  439.    do {
  440.        Assert(cur_match < strstart, "no future");
  441.        match = window + cur_match;
  442.  
  443.        /* Skip to next match if the match length cannot increase
  444.         * or if the match length is less than 2:
  445.         */
  446. #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
  447.        /* This code assumes sizeof(unsigned short) == 2. Do not use
  448.         * UNALIGNED_OK if your compiler uses a different size.
  449.         */
  450.        if (*(ush*)(match+best_len-1) != scan_end ||
  451.            *(ush*)match != scan_start) continue;
  452.  
  453.        /* It is not necessary to compare scan[2] and match[2] since they are
  454.         * always equal when the other bytes match, given that the hash keys
  455.         * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
  456.         * strstart+3, +5, ... up to strstart+257. We check for insufficient
  457.         * lookahead only every 4th comparison; the 128th check will be made
  458.         * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
  459.         * necessary to put more guard bytes at the end of the window, or
  460.         * to check more often for insufficient lookahead.
  461.         */
  462.        scan++, match++;
  463.        do {
  464.        } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
  465.                 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
  466.                 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
  467.                 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
  468.                 scan < strend);
  469.        /* The funny "do {}" generates better code on most compilers */
  470.  
  471.        /* Here, scan <= window+strstart+257 */
  472.        Assert(scan <= window+(unsigned)(WINDOW_SIZE-1), "wild scan");
  473.        if (*scan == *match) scan++;
  474.  
  475.        len = (MAX_MATCH - 1) - (int)(strend-scan);
  476.        scan = strend - (MAX_MATCH-1);
  477.  
  478. #else /* UNALIGNED_OK */
  479.  
  480.        if (match[best_len]   != scan_end  ||
  481.            match[best_len-1] != scan_end1 ||
  482.            *match            != *scan     ||
  483.            *++match          != scan[1])      continue;
  484.  
  485.        /* The check at best_len-1 can be removed because it will be made
  486.         * again later. (This heuristic is not always a win.)
  487.         * It is not necessary to compare scan[2] and match[2] since they
  488.         * are always equal when the other bytes match, given that
  489.         * the hash keys are equal and that HASH_BITS >= 8.
  490.         */
  491.        scan += 2, match++;
  492.  
  493.        /* We check for insufficient lookahead only every 8th comparison;
  494.         * the 256th check will be made at strstart+258.
  495.         */
  496.        do {
  497.        } while (*++scan == *++match && *++scan == *++match &&
  498.                 *++scan == *++match && *++scan == *++match &&
  499.                 *++scan == *++match && *++scan == *++match &&
  500.                 *++scan == *++match && *++scan == *++match &&
  501.                 scan < strend);
  502.  
  503.        len = MAX_MATCH - (int)(strend - scan);
  504.        scan = strend - MAX_MATCH;
  505.  
  506. #endif /* UNALIGNED_OK */
  507.  
  508.        if (len > best_len) {
  509.            match_start = cur_match;
  510.            best_len = len;
  511.            if (len >= nice_match) break;
  512. #ifdef UNALIGNED_OK
  513.            scan_end = *(ush*)(scan+best_len-1);
  514. #else
  515.            scan_end1  = scan[best_len-1];
  516.            scan_end   = scan[best_len];
  517. #endif
  518.        }
  519.    } while ((cur_match = prev[cur_match & WMASK]) > limit
  520.             && --chain_length != 0);
  521.  
  522.    return best_len;
  523. }
  524. #endif /* ASMV */
  525.  
  526. #ifdef DEBUG
  527. /* Check that the match at match_start is indeed a match. */
  528. static void check_match(start, match, length)
  529. IPos start, match;
  530. int length;
  531. {
  532. #if ZMEM
  533.    register j;
  534.    for(j=0; j<length && window[match+j] == window[start+j]; j++);
  535.    if (j < length)
  536. #else
  537.    if (memcmp((char*)window + match, (char*)window + start, length) != 0)
  538. #endif
  539.    {
  540.       fprintf(stderr, " start %d, match %d, length %d\n",
  541.          start, match, length);
  542.       error("invalid match");
  543.    }
  544.    if (verbose > 1) {
  545.       fprintf(stderr,"\\[%d,%d]", start-match, length);
  546.       do { putc(window[start++], stderr); } while (--length != 0);
  547.    }
  548. }
  549. #else
  550. #  define check_match(start, match, length)
  551. #endif
  552.  
  553. /* Add a block of data into the window. Updates strstart and lookahead.
  554.  * IN assertion: lookahead < MIN_LOOKAHEAD.
  555.  * Note: call with either lookahead == 0 or length == 0 is valid
  556.  */
  557. static unsigned fill_window(buffer, length)
  558. char *buffer; unsigned length;
  559. {
  560.    register unsigned n, m;
  561.    unsigned more = length;
  562.  
  563.    /* Amount of free space at the end of the window. */
  564.    if (WINDOW_SIZE - lookahead - strstart < more) {
  565.       more = (unsigned)(WINDOW_SIZE - lookahead - strstart);
  566.    }
  567.    /* If the window is almost full and there is insufficient lookahead,
  568.     * move the upper half to the lower one to make room in the upper half.
  569.     */
  570.    if (strstart >= WSIZE+MAX_DIST) {
  571. #ifdef ZMEM
  572.       n = 0; do window[n] = window[n+WSIZE]; while (++n < WSIZE);
  573. #else
  574.       memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
  575. #endif
  576.       match_start -= WSIZE;
  577.       strstart    -= WSIZE; /* we now have strstart >= MAX_DIST: */
  578.  
  579.       block_start -= (long) WSIZE;
  580.  
  581.       for (n = 0; n < HASH_SIZE; n++) {
  582.          m = head[n];
  583.          head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
  584.       }
  585.       for (n = 0; n < WSIZE; n++) {
  586.          m = prev[n];
  587.          prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
  588.          /* If n is not on any hash chain, prev[n] is garbage but
  589.             its value will never be used. */
  590.       }
  591.       if ((more += WSIZE) > length) more = length;
  592.    }
  593.    if (more) {
  594. #ifdef ZMEM
  595.       register char *p = (char*)window+strstart+lookahead;
  596.  
  597.       n = more; do *p++ = *buffer++; while (--n);
  598. #else
  599.       (void)memcpy((char*)window+strstart+lookahead, buffer, more);
  600. #endif
  601.       lookahead += more;
  602.    }
  603.    return more;
  604. }
  605.  
  606. /* Flush the current block, with given end-of-file flag.
  607.    IN assertion: strstart is set to the end of the current match. */
  608. #define FLUSH_BLOCK(eof) flush_block(block_start >= 0L ?\
  609.         (char*)&window[(unsigned)block_start] : \
  610.         (char*)NULL, (long)strstart - block_start, (eof))
  611.  
  612. /* Processes a new input block.
  613.  * This function does not perform lazy evaluationof matches and inserts
  614.  * new strings in the dictionary only for unmatched strings or for short
  615.  * matches. It is used only for the fast compression options. */
  616. int fast_deflate(buffer, length)
  617. char *buffer; unsigned length;
  618. {
  619.    IPos hash_head; /* head of the hash chain */
  620.    int flush;      /* set if current block must be flushed */
  621.    unsigned accepted = 0;
  622.  
  623.    do {
  624.       /* Make sure that we always have enough lookahead, except
  625.        * at the end of the input file. We need MAX_MATCH bytes
  626.        * for the next match, plus MIN_MATCH bytes to insert the
  627.        * string following the next match. */
  628.       accepted += fill_window(buffer+accepted, length-accepted);
  629.       if (lookahead <= minlookahead) break;
  630.       if (!uptodate) {
  631.          match_length = 0; init_hash(); uptodate = 1;
  632.       }
  633.       while (lookahead > minlookahead) {
  634.          /* Insert the string window[strstart .. strstart+2] in the
  635.           * dictionary, and set hash_head to the head of the hash chain:
  636.           */
  637.          INSERT_STRING(strstart, hash_head);
  638.  
  639.          /* Find the longest match, discarding those <= prev_length.
  640.           * At this point we have always match_length < MIN_MATCH */
  641.          if (hash_head != NIL && strstart - hash_head <= MAX_DIST) {
  642.             /* To simplify the code, we prevent matches with the string
  643.              * of window index 0 (in particular we have to avoid a match
  644.              * of the string with itself at the start of the input file).
  645.              */
  646.             match_length = longest_match(hash_head);
  647.             /* longest_match() sets match_start */
  648.             if (match_length > lookahead) match_length = lookahead;
  649.          }
  650.          if (match_length >= MIN_MATCH) {
  651.             check_match(strstart, match_start, match_length);
  652.  
  653.             flush = ct_tally(strstart-match_start, match_length - MIN_MATCH);
  654.  
  655.             lookahead -= match_length;
  656.  
  657.             /* Insert new strings in the hash table only if the match length
  658.              * is not too large. This saves time but degrades compression.
  659.              */
  660.             if (match_length <= max_insert_length) {
  661.                 match_length--; /* string at strstart already in hash table */
  662.                 do {
  663.                     strstart++;
  664.                     INSERT_STRING(strstart, hash_head);
  665.                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  666.                      * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
  667.                      * these bytes are garbage, but it does not matter since
  668.                      * the next lookahead bytes will be emitted as literals.
  669.                      */
  670.                 } while (--match_length != 0);
  671.                 strstart++;
  672.             } else {
  673.                 strstart += match_length;
  674.                 match_length = 0;
  675.                 ins_h = window[strstart];
  676.                 UPDATE_HASH(ins_h, window[strstart+1]);
  677. #if MIN_MATCH != 3
  678.                 Call UPDATE_HASH() MIN_MATCH-3 more times
  679. #endif
  680.             }
  681.          } else {
  682.             /* No match, output a literal byte */
  683.             Tracevv((stderr,"%c",window[strstart]));
  684.             flush = ct_tally (0, window[strstart]);
  685.             lookahead--;
  686.             strstart++;
  687.          }
  688.          if (flush) {
  689.             if (FLUSH_BLOCK(0) == -1L) goto error;
  690.             block_start = strstart;
  691.          }
  692.       }
  693.    } while (accepted < length);
  694.    if (!minlookahead) {/* eof achieved */
  695.       if (FLUSH_BLOCK(1) == -1L) goto error;
  696.    }
  697.    return accepted;
  698. error:
  699.    return -1;
  700. }
  701.  
  702. /* Same as above, but achieves better compression. We use a lazy
  703.  * evaluation for matches: a match is finally adopted only if there is
  704.  * no better match at the next window position.  */
  705. int lazy_deflate(buffer, length)
  706. char *buffer; unsigned length;
  707. {
  708.    IPos hash_head;          /* head of hash chain */
  709.    IPos prev_match;         /* previous match */
  710.    int flush;               /* set if current block must be flushed */
  711.    register unsigned ml = match_length; /* length of best match */
  712. #ifdef DEBUG
  713.    extern ulg isize;        /* byte length of input file, for debug only */
  714. #endif
  715.    unsigned accepted = 0;
  716.  
  717.    /* Process the input block. */
  718.    do {
  719.       /* Make sure that we always have enough lookahead, except
  720.        * at the end of the input file. We need MAX_MATCH bytes
  721.        * for the next match, plus MIN_MATCH bytes to insert the
  722.        * string following the next match. */
  723.       accepted += fill_window(buffer+accepted, length-accepted);
  724.       if (lookahead <= minlookahead) break;
  725.       if (!uptodate) {
  726.          ml = MIN_MATCH-1; /* length of best match */
  727.          init_hash();
  728.          uptodate = 1;
  729.       }
  730.       while (lookahead > minlookahead) {
  731.          INSERT_STRING(strstart, hash_head);
  732.  
  733.          /* Find the longest match, discarding those <= prev_length. */
  734.          prev_length = ml, prev_match = match_start;
  735.          ml = MIN_MATCH-1;
  736.  
  737.          if (hash_head != NIL && prev_length < max_lazy_match &&
  738.              strstart - hash_head <= MAX_DIST) {
  739.             /* To simplify the code, we prevent matches with the string
  740.              * of window index 0 (in particular we have to avoid a match
  741.              * of the string with itself at the start of the input file).
  742.              */
  743.             ml = longest_match (hash_head);
  744.             /* longest_match() sets match_start */
  745.             if (ml > lookahead) ml = lookahead;
  746.  
  747.             /* Ignore a length 3 match if it is too distant: */
  748.             if (ml == MIN_MATCH && strstart-match_start > TOO_FAR){
  749.                /* If prev_match is also MIN_MATCH, match_start is garbage
  750.                   but we will ignore the current match anyway. */
  751.                ml--;
  752.             }
  753.          }
  754.          /* If there was a match at the previous step and the current
  755.             match is not better, output the previous match: */
  756.          if (prev_length >= MIN_MATCH && ml <= prev_length) {
  757.  
  758.             check_match(strstart-1, prev_match, prev_length);
  759.  
  760.             flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);
  761.  
  762.             /* Insert in hash table all strings up to the end of the match.
  763.              * strstart-1 and strstart are already inserted.
  764.              */
  765.             lookahead -= prev_length-1;
  766.             prev_length -= 2;
  767.             do {
  768.                strstart++;
  769.                INSERT_STRING(strstart, hash_head);
  770.                /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  771.                 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
  772.                 * these bytes are garbage, but it does not matter since the
  773.                 * next lookahead bytes will always be emitted as literals.
  774.                 */
  775.             } while (--prev_length != 0);
  776.             match_available = 0;
  777.             ml = MIN_MATCH-1;
  778.             strstart++;
  779.             if (flush) {
  780.                if (FLUSH_BLOCK(0) == -1L) goto error;
  781.                block_start = strstart;
  782.             }
  783.  
  784.          } else if (match_available) {
  785.             /* If there was no match at the previous position, output a
  786.              * single literal. If there was a match but the current match
  787.              * is longer, truncate the previous match to a single literal.
  788.              */
  789.             Tracevv((stderr,"%c",window[strstart-1]));
  790.             if (ct_tally (0, window[strstart-1])) {
  791.                 FLUSH_BLOCK(0), block_start = strstart;
  792.             }
  793.             strstart++;
  794.             lookahead--;
  795.          } else {
  796.             /* There is no previous match to compare with,
  797.                wait for the next step to decide. */
  798.             match_available = 1;
  799.             strstart++;
  800.             lookahead--;
  801.          }
  802.          Assert(strstart <= isize && lookahead <= isize, "a bit too far");
  803.       }
  804.    } while (accepted < length);
  805.    if (!minlookahead) {/* eof achieved */
  806.       if (match_available) ct_tally (0, window[strstart-1]);
  807.       if (FLUSH_BLOCK(1) == -1L) goto error;
  808.    }
  809.    match_length = ml;
  810.    return accepted;
  811. error:
  812.    return -1;
  813. }
  814.